package com.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {
    //存储顶点的集合
    private ArrayList<String> vertexList;
    //存储相应的邻接矩阵
    private int[][] edges;
    //表示边的数目
    private int numOfEdges;
    //记录结点是否被访问
    private boolean[] isVisited;

    /**
     * @param n :初始化图时定义图中节点个数
     */
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    /**
     * 得到第一个邻接节点的下标，如果不存在，返回-1
     */
    public int getFirstVertexIndex(int index){
        for(int i = 0 ; i < vertexList.size();i++){
            if(edges[index][i] > 0){
                return i;
            }
        }
        return -1;
    }
    /**
     * 如果当前结点的第一个邻接结点已经被访问，则返回当前结点
     * 并从第一个邻接结点开始，继续查找下一个邻接结点
     * @param v1 当前结点下标
     * @param v2 当前结点的邻接结点的下标
     */
    public int getNextNeighbor(int v1,int v2){
        for(int i = v2 + 1;i<vertexList.size();i++){
            if(edges[v1][i] > 0){
                return i;
            }
        }
        return  -1;
    }

    /**
     * 深度遍历
     * @param isVistied 查看该结点是否已经被访问
     * @param i
     */
    private void dfs(boolean[] isVistied,int i){
        //输出该结点并将该结点置为已访问
        System.out.print(getValueByIndex(i) + " ");
        isVistied[i] = true;
        //查找该结点的第一个邻接结点
        int w = getFirstVertexIndex(i);
        while (w != -1){
            //如果存在邻接结点，则以该结点进行深度遍历
            if(!isVistied[w]){
                dfs(isVistied,w);
            }
            //如果该邻接结点已被访问，则下一个邻接结点
            w = getNextNeighbor(i,w);
        }
        //如果该结点没有未被访问的邻接结点，则返回上一个结点，查找该结点的下一个邻接结点
    }

    /**
     * 深度遍历，调用重载方法
     */
    public void dfs(){
        //考虑非连通图的情况，需要对这些结点进行遍历
        for(int i = 0;i<getNumOfVertex();i++){
            if(!isVisited[i]){
                dfs(isVisited,0);
            }
        }
        //重置是否被访问的数组
        for(int i = 0;i<isVisited.length;i++){
            isVisited[i] = false;
        }
    }

    private void bfs(boolean[] isVisited,int i){
        int u; //表示队列的头结点对应的下标
        int w; //当前结点的邻接结点
        LinkedList queue = new LinkedList(); //用于保存结点的访问顺序
        //输出该结点并加入到队列中,将该结点置为已访问加
        System.out.print(getValueByIndex(i) + " ");
        isVisited[i] = true;
        queue.addLast(i);

        while(!queue.isEmpty()){
            //取出队列头下标
            u = (Integer)queue.removeFirst();
            w = getFirstVertexIndex(u);
            while( w != -1){
                if(!isVisited[w]){
                    System.out.print(getValueByIndex(w) + " ");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                //继续找下一个结点
                w = getNextNeighbor(u,w);
            }
        }
    }

    public void bfs(){
        //遍历输出非连通图的情况
        for(int i = 0;i<getNumOfVertex();i++){
            if(!isVisited[i]){
                bfs(isVisited,i);
            }
        }
        //重置是否被访问的数组
        for(int i = 0;i<isVisited.length;i++){
            isVisited[i] = false;
        }
    }



    /**
     * 插入顶点
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    /**
     * 添加边
     * v1,v2对应顶对的坐标，如A-0，B-1..
     * weight表示边的权值，通常1表示有边，0表示无边
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;

    }

    public int getNumOfEdges(){
        return numOfEdges;
    }

    public int getNumOfVertex(){
        return vertexList.size();
    }
    /**
     * 返回节点i对应的下标
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    /**
     * 返回两个节点间边的权值
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    /**
     * 显示图对应的邻接矩阵
     */
    public void showGraph(){
        for(int edge[]:edges){
            System.out.println(Arrays.toString(edge));
        }
    }
}
